'''
Created on Mar 6, 2011

@author: Roni
'''

class RadixTree(object):
    '''
    Radix tree implementation for storing a set of cliques
    '''


    def __init__(self):
        '''
        Constructor
        '''
        self.root = None
        
    def insert(self,key,value):
        # If this is the first element - just add it to the root of the tree
        if self.root is None:
            self.root = RadixTreeNode(key,value)
            return
        
        tree_node = self.root
        parent_tree_node = None
        while True:            
            common_prefix = self.__common_prefix(tree_node, key)
            common_prefix_size = len(common_prefix)
            # If node is a prefix of the tree node - it is either equal or should be a parent of it
            if common_prefix_size==len(key):
                if len(key)<len(tree_node): # node should be a parent of tree_node
                    new_tree_node = RadixTreeNode(key,value)
                    new_tree_node.children.append(tree_node)
                    if parent_tree_node is None: # If tree_node is the root
                        self.root = new_tree_node
                    else:
                        parent_tree_node.children.remove(tree_node)
                        parent_tree_node.children.append(new_tree_node)
                    
                    # If there is a common prefix - trim tree node (if is needed since common prefix maybe empty)
                    if common_prefix_size>0:
                        tree_node.trim_left(common_prefix_size) # No need to store the common prefix
                # Otherwise, node and tree_node are equal. 
                # If tree_node do not have a value (happens when it was created only to support its children) - set its value now.
                elif tree_node.value is None:
                    tree_node.value = value
                return
            else: # common_prefix is shorter than node
                key = key[common_prefix_size:] # Trim all the nodes in the common prefix
                
                # If the common prefix is exactly tree node, then current node needs to go down the trie
                if common_prefix_size==len(tree_node):                    
                    next_char = key[0]
                    # Choose which child first the current node
                    child_found = False
                    for child in tree_node.children:
                        if child[0]==next_char:
                            parent_tree_node = tree_node
                            tree_node = child
                            child_found=True
                            break
                    # No child was found fitting - need to add the current node as a new child
                    if child_found==False:
                        tree_node.children.append(RadixTreeNode(key,value))
                        return
                    
                else: # If tree node is shorter than the common prefix - tree node and current node need a joint parent
                    new_tree_parent = RadixTreeNode(common_prefix, None)
                    new_tree_parent.children.append(tree_node)
                    new_tree_parent.children.append(RadixTreeNode(key,value))
                    
                    # Add new parent to the tree
                    if self.root==tree_node:
                        self.root = new_tree_parent
                    else:    
                        parent_tree_node.children.remove(tree_node)
                        parent_tree_node.children.append(new_tree_parent)
                    return

        
    def find(self,node):
        ''' Searched for the given node in the radix tree '''
        if self.root is None:
            return None
        
        tree_node = self.root

        # If tree_node is a parent of node
        while True:
            common_prefix = self.__common_prefix(tree_node, node)
            common_prefix_size = len(common_prefix)
            
            # If common prefix does not contain all the values in tree node - the searched node is not there
            if common_prefix_size<len(tree_node):
                return None # Tree node is not in this data structure
            
            # If tree node is exactly equal to node - return it
            if common_prefix_size==len(tree_node) and common_prefix_size==len(node):
                if tree_node.value is None:
                    return None
                else:
                    return tree_node
            
            # Choose which child first the current node
            node = node[common_prefix_size:]
            next_char = node[0]            
            child_found = False
            for child in tree_node.children:
                if child[0]==next_char:
                    tree_node = child
                    child_found=True
                    break  
            
            # If no fitting child was found - then node is not contained in this container          
            if child_found==False:
                return None
            
        
    def __common_prefix(self,node, new_node):
        ''' Return the largest common prefix of node and new_node '''
        min_size = min(len(node),len(new_node))
        common_prefix = []
        for i in xrange(min_size):
            if node[i]==new_node[i]:
                common_prefix.append(node[i])
            else:
                break
        return common_prefix
                    
        
class RadixTreeNode(object):
    def __init__(self,key,value):
        self.key = key
        self.value = value
        self.children = []
        
    def __len__(self):
        return self.key.__len__()
    
    def __getitem__(self,index):
        return self.key[index]
    
    def __str__(self):
        return self.key.__str__()
    
    def trim_left(self,leftmost_index):
        self.key=self.key[:leftmost_index]

        